package arithmetic1.search;

/*
    差值查找
        mid=start+(end-start)*(key-arr[start])/(arr[end]-arr[start])
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int arr[]={0,1,2,3,4,5,6,7,8,9};
        int index=insertValueSearch(arr,8);
        System.out.println(index);
    }

    //插值查找
    public static int insertValueSearch(int arr[],int start,int end,int key){
        if(start<=end && key>=arr[start] && key<=arr[end]){
            //插值查找核心公式
            int mid=start+(end-start)*(key-arr[start])/(arr[end]-arr[start]);
            if(arr[mid]==key){
                return mid;
            }else if(arr[mid]<key){ //向右查找
                return insertValueSearch(arr,mid+1,end,key);
            }else {     //向左查找
                return insertValueSearch(arr,start,mid-1,key);
            }
        }
        return -1;
    }

    //重载
    public static int insertValueSearch(int arr[],int key){
        return insertValueSearch(arr,0,arr.length-1,key);
    }
}
